package cn.xiaolang.function.data_structure;

import java.util.HashMap;
import java.util.Map;

/**
 * 回文排列
 * <p>
 * 回文串是指正反两个方向都一样的单词或短语。排列是指字母的重新排列。
 * <p>
 * 回文串不一定是字典当中的单词。
 * <p>
 *  
 * <p>
 * 示例1：
 * <p>
 * 输入："tactcoa"
 * 输出：true（排列有"tacocat"、"atcocta"，等等）
 *
 * @author fuhw/Dean
 * @date 2020-06-09
 */
public class No3CharPermutePalindrome {

    public static void main(String[] args) {
        System.out.println(canPermutePalindromeByArray("tactcoa"));
    }

    /**
     * 思路：
     * 1 每个字符出现的次数为偶数
     * 2 或者有且只有一个字符出现的次数为奇数时, 是回文的排列; 否则不是.
     * 字符出现次数为奇数的个数为0或者1
     */
    public static boolean canPermutePalindromeByMap(String s) {
        Map<Character, Integer> strMap = new HashMap<>();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (strMap.containsKey(c)) {
                strMap.remove(c);
            } else {
                strMap.put(c, 1);
            }
        }
        return strMap.size() == 0 || strMap.size() == 1;
    }

    /**
     * 思路：
     * 1 用数组mock一个map结构
     * 2 count字符出现次数为奇数的个数为0或者1
     */
    public static boolean canPermutePalindromeByArray(String s) {
        int[] map = new int[256];
        int count = 0;
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            map[c]++;
            if (map[c] > 1) {
                count--;
                // 数值置0
                map[c] = 0;
            } else {
                count++;
            }

        }
        return count <= 1;
    }

}
